package com.zlk.algorithm.algorithm.dynamicPlan.mutiKnapsack75;

import java.io.*;

// 多重背包通过二进制分组转化成01背包(模版)
// 宝物筛选
// 一共有n种货物, 背包容量为t
// 每种货物的价值(v[i])、重量(w[i])、数量(c[i])都给出
// 请返回选择货物不超过背包容量的情况下，能得到的最大的价值
// 测试链接 : https://www.luogu.com.cn/problem/P1776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code02_BoundedKnapsackWithBinarySplitting {

    public static int MAXN = 1001;

    public static  int t ;
    public static  int n;//原始物品个数
    public static  int m;//二进制拆分个数
    public static int[] V = new int[MAXN];
    public static int[] W = new int[MAXN];

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(reader);
        PrintWriter out =new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken()!=-1){
            n =(int) in.nval;
            in.nextToken();
            t =(int) in.nval;
            m = 0;
            for (int i = 1,value, weight, cnt; i <=n ; i++) {
                in.nextToken();value=(int)in.nval;
                in.nextToken();weight=(int)in.nval;
                in.nextToken();cnt=(int)in.nval;
                // 整个文件最重要的逻辑 : 二进制分组
                // 一般都使用这种技巧，这段代码非常重要
                // 虽然时间复杂度不如单调队列优化的版本
                // 但是好写，而且即便是比赛，时间复杂度也达标
                // 二进制分组的时间复杂度为O(log cnt)
                for (int k = 1; k <= cnt; k <<= 1) {
                    V[++m] = k * value;
                    W[m] = k * weight;
                    cnt -= k;
                }
                if (cnt > 0) {
                    V[++m] = cnt * value;
                    W[m] = cnt * weight;
                }
            }
            out.println(compute2());
        }
        out.flush();
        out.close();
        reader.close();
    }

    private static int compute() {
        int[][] dp = new int[m+1][t+1];
        for (int i = 1; i <=m ; i++) {
            int w = W[i];
            int v = V[i];
            for (int j = 0; j <=t ; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=w){
                    dp[i][j] =Math.max(dp[i][j],dp[i][j-w]+v);
                }
            }
        }
        return dp[m][t];
    }

    private static int compute2() {
        int[] dp = new int[t+1];
        for (int i = 1; i <=m ; i++) {
            int w = W[i];
            int v = V[i];
            for (int j = t; j >=w ; j--) {
                dp[j]=Math.max(dp[j],dp[j-w]+v);
            }
        }
        return dp[t];
    }

}
